package com.str.graphs;
public class Floyd {
  private static void printout(Graph g, int[][] d) {
    for (int i=0; i<g.n(); i++) {
      for (int j=0; j<g.n(); j++)
        System.out.print(d[i][j] + "  ");
      System.out.println();
    }
  }

  // Floyd's all-pairs shortest paths algorithm
  public static void floyd(Graph g) {
    int[][] d = new int[g.n()][g.n()];  // Store distances
    for (int i=0; i<g.n(); i++)      // Initialize D with weights
      for (int j=0; j<g.n(); j++)
        d[i][j] = g.weight(i, j);
    for (int k=0; k<g.n(); k++)     // Compute all k paths
      for (int i=0; i<g.n(); i++)
        for (int j=0; j<g.n(); j++)
	      if ((d[i][k] != Integer.MAX_VALUE) &&
	          (d[k][j] != Integer.MAX_VALUE) &&
	      	  (d[i][j] > (d[i][k] + d[k][j])))
	        d[i][j] = d[i][k] + d[k][j];
    printout(g, d);
  } 
}
